class Solution {
public:
    int dfs(TreeNode* root, long long targetSum) {
        // 以root为根，向下延伸的路径中，有多少符合题意
        if (!root) return 0;
        
        int ret = 0;

        if (root->val == targetSum) {
            ret++;
        } 

        ret += dfs(root->left, targetSum - root->val);
        ret += dfs(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) return 0;

        int res = dfs(root, targetSum);
        res += pathSum(root->left, targetSum);
        res += pathSum(root->right, targetSum);

        return res;
    }
};